package letcode.oneQuestionPerDay._202004._26;

import letcode.util.ListNode;

import java.util.*;

/**
 * @Description: 合并k个排序链表
 * @Date: 2020/4/26
 * @Author: 许群星
 */
public class MergeKLinkedList {
    public static void main(String[] args) {
        ListNode[] lists=new ListNode[3];
        ListNode first=new ListNode(1);
        first.next=new ListNode(3);
        first.next.next=new ListNode(4);

        ListNode second=new ListNode(1);
        second.next=new ListNode(4);
        second.next.next=new ListNode(5);

        ListNode third=new ListNode(2);
        third.next=new ListNode(6);

        lists[0]=second;
        lists[1]=first;
        lists[2]=third;

        ListNode head=mergeKLists(lists);
        System.out.println(head.val);
        System.out.println(head.next.val);
        System.out.println(head.next.next.val);
        System.out.println(head.next.next.next.val);
        System.out.println(head.next.next.next.next.val);
        System.out.println(head.next.next.next.next.next.val);
        System.out.println(head.next.next.next.next.next.next.val);
        System.out.println(head.next.next.next.next.next.next.next.val);
    }
    //提供方法
    //自己想法从开始就是错的，一直想的是如何直接合并多个。看了题解发现，应该依次开始
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        //创建小根堆
        PriorityQueue<ListNode> queue=new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return (o1.val-o2.val);
            }
        });
        //遍历数组，每个节点都放入堆中
        for (int i = 0; i < lists.length; i++) {
            while (lists[i]!=null){
                queue.add(lists[i]);
                lists[i]=lists[i].next;
            }
        }
        ListNode dummy=new ListNode(-1);
        ListNode head=dummy;
        //从堆中取出节点并串联起来
        while (!queue.isEmpty()) {
            dummy.next=queue.poll();
            dummy=dummy.next;
        }
        dummy.next=null;
        return head.next;
    }

}
/*
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */